package leetcode.code0127;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Solution2 extends Solution127 {

	@Override
	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
		Set<String> set = new HashSet<>(wordList);
		if (!set.contains(endWord))
			return 0;
		Map<String, Integer> dp = new HashMap<>();
		int ans = this.f(beginWord, endWord, set, dp);
		dp = new HashMap<>();
		set.add(beginWord);
		ans = Math.min(ans, this.f(endWord, beginWord, set, dp));
		return ans == Integer.MAX_VALUE ? 0 : ans;
	}

	private int f(String beginWord, String endWord, Set<String> set, Map<String, Integer> dp) {
		if (beginWord.equals(endWord)) {//endsWith
			return 1;
		}
//		Integer ans = dp.get(beginWord);
//		if (ans != null)
//			return ans;
		Integer ans = Integer.MAX_VALUE;
		StringBuffer sb = new StringBuffer(beginWord);
		for (int i = 0; i < beginWord.length(); i++) {
			char c = sb.charAt(i);
			for (int j = 'a'; j <= 'z'; j++) {
				sb.setCharAt(i, (char) j);
				if ((char) j != c && set.contains(sb.toString())) {
					set.remove(sb.toString());
					ans = Math.min(ans, this.f(sb.toString(), endWord, set, dp));
					set.add(sb.toString());
				}
			}
			sb.setCharAt(i, c);
		}
		ans = ans != Integer.MAX_VALUE ? ans + 1 : Integer.MAX_VALUE;
//		dp.put(beginWord, ans);
		return ans;
	}

	Map<String, Integer> wordId = new HashMap<>();
	List<List<Integer>> edge = new ArrayList<>();
	int nodeNum = 0;

	public int ladderLength1(String beginWord, String endWord, List<String> wordList) {
		for (String word : wordList) {
			addEdge(word);
		}
		addEdge(beginWord);
		if (!wordId.containsKey(endWord)) {
			return 0;
		}
		int[] dis = new int[nodeNum];
		Arrays.fill(dis, Integer.MAX_VALUE);
		int beginId = wordId.get(beginWord), endId = wordId.get(endWord);
		dis[beginId] = 0;

		Queue<Integer> que = new LinkedList<>();
		que.offer(beginId);
		while (!que.isEmpty()) {
			int x = que.poll();
			if (x == endId) {
				return dis[endId] / 2 + 1;
			}
			for (int it : edge.get(x)) {
				if (dis[it] == Integer.MAX_VALUE) {
					dis[it] = dis[x] + 1;
					que.offer(it);
				}
			}
		}
		return 0;
	}

	public void addEdge(String word) {
		addWord(word);
		int id1 = wordId.get(word);
		char[] array = word.toCharArray();
		int length = array.length;
		for (int i = 0; i < length; ++i) {
			char tmp = array[i];
			array[i] = '*';
			String newWord = new String(array);
			addWord(newWord);
			int id2 = wordId.get(newWord);
			edge.get(id1).add(id2);
			edge.get(id2).add(id1);
			array[i] = tmp;
		}
	}

	public void addWord(String word) {
		if (!wordId.containsKey(word)) {
			wordId.put(word, nodeNum++);
			edge.add(new ArrayList<Integer>());
		}
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug5();
		so.debug3();

	}

}
